/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/132-pattern
   @Language: C++
   @Datetime: 19-06-11 15:44
   */

// Method 1, Time 201ms
class Solution {
public:
	/**
	 * @param nums: a list of n integers
	 * @return: true if there is a 132 pattern or false
	 */
	bool find132pattern(vector<int> &nums) {
		// write your code here
		for(int i=nums.size(), ak=INT_MIN; i--;){
			if(nums[i]<ak) return true;
			for(int k=i+1; k<nums.size() && nums[i]>nums[k]; ak=nums[k++]);
		}
		return false;
	}
};

// Method 2, max stack, Time 50ms
class Solution {
public:
	/**
	 * @param nums: a list of n integers
	 * @return: true if there is a 132 pattern or false
	 */
	bool find132pattern(vector<int> &nums) {
		// write your code here
		stack<int> s;
		for(int i=nums.size(), ak=INT_MIN; i--; s.push(nums[i])){
			if(nums[i]<ak) return true;
			for(; s.size() && nums[i]>s.top(); s.pop())
				ak=s.top();
		}
		return false;
	}
};
